Lưu trữ cấu trúc cây nhị phân

Để biểu diễn cây nhị phân ta dùng cấu trúc Nút (Node). Mỗi Nút là một đỉnh của cây, gồm ba trường, một trường V a l u e {\displaystyle Value} chứa thông tin về nút đó. Hai trường L e f t {\displaystyle Left} và R i g h t {\displaystyle Right} trỏ tới các nút con của đỉnh đó. Ngoài ra còn một con trỏ là R o o t {\displaystyle Root} trỏ tới nút gốc.

Cây nhị phân ở trong bài có thể biểu diễn như sau:

Root=AA.Value="A",A.Left=B;A.Right=CB.Value="B",B.Left=D;B.Right=EC.Value="C",C.Left=F;C.Right=GD.Value="D",D.Left=Null;D.Right=NullE.Value="E",E.Left=Null;E.Right=NullF.Value="F",F.Left=Null;F.Right=NullG.Value="G",G.Left=Null;G.Right=Null

Chú ý: Phân biệt ký hiệu A, B,... chỉ nút và "A","B",... chỉ giá trị nút

Lưu trữ cấu trúc cây tổng quát

Khi biểu diễn cấu trúc cây tổng quát, vì mỗi nút có thể có nhiều con, số con có thể khác nhau, nên ta không dùng cho mỗi nút con một liên kết đến nút cha mà với mỗi nút vẫn chỉ dành hai liên kết, một liên kết (trường C h i l d {\displaystyle Child} ) trỏ đến nút con đầu bên trái của nó, một liên kết (trường N e x t {\displaystyle Next} )trỏ đến nút cùng cha kề bên phải nó. Nếu coi liên kết trường C h i l d {\displaystyle Child} như liên kết L e f t {\displaystyle Left} , liên kết N e x t {\displaystyle Next} như liên kết R i g h t {\displaystyle Right} ta có một cây nhị phân tương đương với cây tổng quát.

Ví dụ

• Cây tổng quát

         A       / | \     B   C  D    / \     |  E    F    G

• Cây nhị phân tương đương

          A         /        B       /  \      E   C       \    \       F     D            /            G

• Lưu trữ của cây tổng quát như sau

Root=AA.Value="A",A.Child=B,A.Next=NullB.Value="B",B.Child=E,B.Next=CC.Value="C",C.Child=Null,C.Next=DD.Value="D",D.Child=G,D.Next=NullE.Value="E",E.Null,E.Next=FF.Value="F",F.Child=Null,F.Next=NullG.Value="G",D.Child=Null,G.Next=Null